This invention relates to data processing systems having a time-shared data bus over which a plurality of devices send messages in a time-shared fashion, and more particularly to control circuits for resolving the sequence by which the bus is time-shared when several of the devices request to use the bus at the same time.
To put this invention into perspective, reference should be made to FIGS. 1 and 2A-2C wherein one data processing system incorporating a prior art time-shared data bus and its operation is illustrated. In the system of FIG. 1, a first plurality of N devices (labeled Device 1A through Device NA) couple to a first time-shared data bus (labeled Bus A), and a second plurality of M devices (labeled Device 1B through Device MB) couple to a second time-shared data bus (labeled Bus B).
These devices send messages to each other over the respective bus to which they are connected in a time-shared fashion. Also, the ith device on bus B (device IB) connects to both bus A and bus B; and it operates to receive messages from devices on bus A and pass those messages to devices on bus B.
Note that the exact makeup of each of the devices in FIG. 1 is unimportant to this invention. That is, the devices in FIG. 1 can be any mix of a wide variety of data processors and peripherals, such as tapes and disks and card readers and printers for example. However, what is important with regard to this invention is the manner in which the devices are given access to their respective buses; and how conflicts are resolved when several devices request to use one bus at the same time.
In the prior art, this bus contention problem was often handled by providing a bus controller (BUS CNT'L) along with each bus as illustrated in FIG. 1. Each device requested to use the bus by sending a bid signal to the bus controller; and the bus controller in turn sent a signal back to one of those bidding devices indicating that the bus was available for its use. To pick that one device, all of the devices on the bus bid with a pre-assigned priority (e.g.,--device 1A had the highest priority, device 2A had the next highest priority, etc.). And the bus controller gave the bus to the one device that was bidding with the highest priority.
FIG. 2A shows the sequence of operation of the above-described bus controller. That figure contains two graphs with "time" on the horizontal axis, "bidding devices" on one vertical axis, and "device given the bus" on the other vertical axis. Also, time on the horizontal axis is divided into cycles labeled CY1, CY2, . . . , etc.
During cycle 1, devices 1, 2, and N are illustrated as bidding for the same bus (e.g., bus A). Of those bidding devices, device 1 has the highest priority; so it is given the bus during cycle 2. Then during cycle 2, devices 2 and N again bid for the bus. Between devices 2 and N, device 2 has the highest priority; so it is granted the use of the bus during cycle 3. Then during cycle 3, devices 4 and 7 start to bid for the bus along with the previously bidding device N. Device 4 is given the bus during cycle 4 because it is the highest bidding device during the preceding cycle 3. Device 7 is given the bus during cycle 5 because it is the highest priority bidding device during the preceding cycle 4.
From this FIG. 2A sequence it can be seen that the lowest priority device N keeps bidding for the bus but it never gets to use the bus. This is because devices of higher priority are simultaneously bidding for the bus. Consequently, device N gets "starved out" from using the bus for an indefinite period of time; which eventually causes data buffers in that device to "overflow" and/or "underflow".
This "starve out" problem has been resolved in the prior art by modifying the bus controller to take a "snapshot" of all of the devices that simultaneously bid for the use of the bus and thereafter only grant the use of the bus to those devices whose bids are in the snapshot. Suppose, for example, that five different devices simultaneously bid during one cycle for the use of the bus. In that case, the bus controller would allocate the next five cycles to those five devices; and if any other devices requested the bus during those five cycles, they would be ignored. Then, after the five cycles had passed, the bus controller would take a new snapshot and the process would be repeated.
This "snapshot" mechanism solves the above-described "starve out" problem of FIG. 2A; but it also creates two new problems that are illustrated in FIGS. 2B and 2C. FIG. 2B shows that while a low priority device can no longer be starved off of the bus indefinitely, it still can be temporarily "locked out" from the bus for as many as 2(N-1) cycles. Further, FIG. 2C shows that even the highest priority device on the bus may now be locked out from the bus for as many as (N-1) cycles. Consequently, overflows and underflows will occur in both the low priority and high priority devices unless they contain enough buffering to continue their operations during these locked-out cycles.
Consider now in detail the sequence of FIG. 2B. In that sequence, all of the devices except device N bid for the use of the bus during cycle 1 and a snapshot of those bidding devices is taken. Then in cycle 2, device N desires the use of the bus; but its bid is ignored by the bus controller (as indicated by the encircled N) because of the preceding snapshot. That is, cycles 2, 3, . . . N are already allocated to those N-1 devices which requested the use of the bus during cycle 1.
Thereafter, during cycle N, a new snapshot is taken. This time, assume that all of the devices along with device N are requesting the use of the bus. Then cycles N+1 through 2N will be allocated to the devices having their bids in the second snapshot. And device N will be allocated cycle 2N because it has the lowest priority. Thus, a total of 2(N-1) cycles occur between the time when device N initially wanted to use the bus and the time when it actually obtained the use of the bus.
Next, consider in detail the sequence of FIG. 2C, which is the largest lockout sequence for the highest priority device 1. There, all of the devices except device 1 bid for the use of the bus during the first cycle; and a snapshot of those bids is taken by the bus controller. Then, during cycle 2, device 1 wants to use the bus but it cannot because cycles 2 through N are already allocated to those devices whose bids are stored in the preceding snapshot. Subsequently, during cycle N a new snapshot is taken; and device 1, being the highest priority device, will be given the bus in the next cycle. But a total of (N-1) cycles occur between the time that device 1 initially wanted to get onto the bus and the time that it actually got the bus.
These problems as described above in conjunction with FIGS. 2A, 2B, and 2C, also occur in a single bus system as well as the dual bus system of FIG. 1. But in the dual bus system, they give rise to still other problems. To understand this dual bus problem, consider the case where devices on bus A are sending messages through device IB to other devices on bus B. A question then arises as to what priority device IB should be given on bus B in order to minimize the lockout time in all of the other devices.
Suppose, for example, that device IB is given the highest priority on bus B. In that case, messages from high priority devices on bus A will retain their high priority on bus B and so overflows/underflows in the high priority device on bus A will be minimized. However, if several low priority devices on bus A also transmit messages through device IB to other devices on bus B, then messages from those low priority devices will also be given priority over all messages from devices on bus B. So overflows/underflows in high priority devices on bus B will be increased because a high priority device on bus B will now have to wait for all of the low priority devices on bus A before it is given the bus.
Conversely, suppose that device IB is assigned a low priority on bus B. In that case, messages from low priority devices on bus A that pass through device IB to other devices on bus B will retain their low priority. So the chances for an overflow/underflow of a high priority device on bus B will be minimized. However, messages from high priority devices on bus A that pass through device IB to devices on bus B will also be given a low priority on bus B. So the chances of overflows/underflows occurring in the high priority devices on bus A will be greatly increased.
Accordingly, it is a primary object of this invention to provide an improved circuit for incorporation into a device on a time shared bus to control the sequence by which that device bids for the use of the bus.
Another object of the invention is to provide an improved device on a time-shared data bus which bids for the use of that bus in a manner heretofore not attained.
Another object of the invention is to provide an improved system comprised of a plurality of devices coupled to a time shared bus wherein the longest lockout time for each and every device on the bus is less than that attained in the prior art.
Still another object of the invention is to provide an improved dual bus system comprised of first and second buses having respective pluralities of devices coupled thereto with one device being coupled to receive messages from the first bus and transfer them to the second bus wherein the longest lockout time for the pluralities of devices is decreased over the prior art.